rtreepack.expr.knnqueries <-
function (dataset="Traj_Point", density.ratio = c(0.1, 10, 100), region.num = 10,
  region.queries = 10, result.max = 100000)
{
    md <- read.csv(paste("data/", dataset, "_density.csv.info", sep = ""))
    d <- read.csv(paste("data/", dataset, "_density.csv", sep = ""), header=F,
      col.names=c("x", "y", "cnt"))
    
    area.total <- (md$maxX - md$minX) * (md$maxY - md$minY)
    density.avg <- sum(d$cnt) / area.total
    d$density <- d$cnt * md$nstrips^2

    candidates <- order(abs(d$density - density.avg * max(density.ratio)))[1:region.num]
    regions.densest <- d[candidates,]
    cnt.avg <- mean(regions.densest$cnt)
    qarea <- list()
    qarea$ratio <- sqrt(cnt.avg / result.max)
    qarea$width <- (md$maxX - md$minX) / md$nstrips * qarea$ratio
    qarea$height <- (md$maxY - md$minY) / md$nstrips * qarea$ratio

    getcsv <- function(filename, xx, yy) {
        colname.list <- c("group", "left", "right", "bottom", "top")
        cols <- lapply(colname.list, function(x) numeric(length(xx)))
        names(cols) <- colname.list
        queries <- do.call("data.frame", cols)
        for (j in 1:length(xx))
            queries[j,] <- c(j, xx[j], xx[j], yy[j], yy[j])
        write.csv(queries, filename, quote=F, row.names=F)
    }

    for (ratio in density.ratio) {
        candidates <- order(abs(d$density - density.avg * ratio))[1:region.num]
        cx <- numeric(0)
        cy <- numeric(0)
        for (candidate in candidates) {
            region <- d[candidate,]
            region.l <- md$minX + (region$x / md$nstrips) * (md$maxX - md$minX)
            region.r <- region.l + (md$maxX - md$minX) / md$nstrips
            region.b <- md$minY + (region$y / md$nstrips) * (md$maxY - md$minY)
            region.t <- region.b + (md$maxY - md$minY) / md$nstrips
            cx <- c(cx, region.l + runif(10) * (region.r - region.l))
            cy <- c(cy, region.b + runif(10) * (region.t - region.b))
        }
        getcsv(paste(dataset, "_", ratio, ".csv.knn", sep = ""), cx, cy)
    }
}

rtreepack.expr.rangequeries <-
function (dataset="Traj_Region", density.ratio = c(1, 10, 100), region.num = 10,
  region.queries = 10, window.num = 100, result.max = 100000)
{
    md <- read.csv(paste("data/", dataset, "_density.csv.info", sep = ""))
    d <- read.csv(paste("data/", dataset, "_density.csv", sep = ""), header=F,
      col.names=c("x", "y", "cnt"))
    
    area.total <- (md$maxX - md$minX) * (md$maxY - md$minY)
    density.avg <- sum(d$cnt) / area.total
    d$density <- d$cnt * md$nstrips^2

    candidates <- order(abs(d$density - density.avg * max(density.ratio)))[1:region.num]
    regions.densest <- d[candidates,]
    cnt.avg <- mean(regions.densest$cnt)
    qarea <- list()
    qarea$ratio <- sqrt(cnt.avg / result.max)
    qarea$width <- (md$maxX - md$minX) / md$nstrips * qarea$ratio
    qarea$height <- (md$maxY - md$minY) / md$nstrips * qarea$ratio

    getcsv <- function(filename, xx, yy) {
        colname.list <- c("group", "left", "right", "bottom", "top")
        cols <- lapply(colname.list, function(x) numeric(length(xx) * window.num))
        names(cols) <- colname.list
        queries <- do.call("data.frame", cols)
        for (i in 1:window.num) {
            w <- qarea$width * sqrt(i / window.num)
            h <- qarea$height * sqrt(i / window.num)
            for (j in 1:length(xx)) {
                queries[window.num * (i - 1) + j,] <-
                  c(i, xx[j] - w / 2, xx[j] + w / 2, yy[j] - h / 2, yy[j] + h / 2)
            }
        }
        write.csv(queries, filename, quote=F, row.names=F)
    }

    for (ratio in density.ratio) {
        candidates <- order(abs(d$density - density.avg * ratio))[1:region.num]
        cx <- numeric(0)
        cy <- numeric(0)
        for (candidate in candidates) {
            region <- d[candidate,]
            region.l <- md$minX + (region$x / md$nstrips) * (md$maxX - md$minX)
            region.r <- region.l + (md$maxX - md$minX) / md$nstrips
            region.b <- md$minY + (region$y / md$nstrips) * (md$maxY - md$minY)
            region.t <- region.b + (md$maxY - md$minY) / md$nstrips
            cx <- c(cx, region.l + runif(10) * (region.r - region.l))
            cy <- c(cy, region.b + runif(10) * (region.t - region.b))
        }
        getcsv(paste(dataset, "_", ratio, ".csv", sep = ""), cx, cy)
    }
}

rtreepack.expr.rangequeries.all <-
function()
{
    rtreepack.expr.rangequeries("Traj_Region", density.ratio = 10^(0:2))
    rtreepack.expr.rangequeries("Traj_Point", density.ratio = 10^(0:2))
    rtreepack.expr.rangequeries("TIGER_Region", density.ratio = (10^(2:4))*2)
    rtreepack.expr.rangequeries("TIGER_Point", density.ratio = (10^(2:4))*2)
}

rtreepack.plot.data.distribution <-
function()
{
    postscript("figures/GPS-Point-Data-Distribution.eps", width = 4.8, height = 4.8,
      paper = "special", horizontal = F)
    a <- read.csv("data/Traj_Point.kpoint.sample", header=F)
    a <- a[sample(nrow(a), 70000),]
    lon <- a$V2
    lat <- a$V4
    par(mar=c(5,5,2,2))
    plot(lon, lat, pch=".", xlim=c(121,121.8), ylim=c(30.8,31.5), cex.axis = 0.8,
      xlab = "Longitude", ylab = "Latitude", cex = 0.2, asp = 1)
    dev.off()

    postscript("figures/TIGER-Point-Data-Distribution.eps", width = 4.8, height = 4.8,
      paper = "special", horizontal = F)
    a <- read.csv("data/TIGER_Point.kpoint.sample", header=F)
    a <- a[sample(nrow(a), 70000),]
    lon <- a$V2
    lat <- a$V4
    par(mar=c(5,5,2,2))
    plot(lon, lat, pch=".", xlim=c(-130,-65), ylim=c(24,50), cex.axis = 0.8,
      xlab = "Longitude", ylab = "Latitude", cex = 0.2, asp = 1.5)
    dev.off()
}

rtreepack.plot.jobtime.detail <-
function()
{
    postscript("figures/Jobtime-Detail.eps", width = 4.8, height = 4.8,
      paper = "special", horizontal = F)
    d <- read.csv("expr/Speedup.csv")
    d$total <- d$time_pre1 + d$time_pack1 + d$time_pre2 + d$time_pack2 + d$time_pack3
    dd <- as.matrix(d[,5:9], byrow = T)
    barplot(t(dd), args.legend = list(x = "topright"), space = rep(c(1,0.2,0.2,0.2), 4),
      ylab = "Execution time (seconds)", xlab = "Number of nodes",
      ylim = c(0, max(d$total * 1.1)),
      legend.text = c("Level 1 preprocessing", "Level 1 packing",
      "Level 2 preprocessing", "Level 2 packing", "Internal packing"))
    axis(1, at = 3.4 + 5.6 * 0:3, tick = F, labels = c(2,4,8,12))
    box()

    text(1.5 + 1.2 * 0:3, d$total[d$nodes == 2] + 300, unique(d$algo), cex = 0.5)
    text(7.1 + 1.2 * 0:3, d$total[d$nodes == 4] + 300, unique(d$algo), cex = 0.5)
    text(12.7 + 1.2 * 0:3, d$total[d$nodes == 8] + 300, unique(d$algo), cex = 0.5)
    text(18.3 + 1.2 * 0:3, d$total[d$nodes == 12] + 300, unique(d$algo), cex = 0.5)
    dev.off()
}

rtreepack.plot.query.performance <-
function (filename = "expr/TIGER_Region_200.csv.range.result", knn = F, epsfile = NA) 
{
    d <- read.csv(filename)
    if (knn)
        dd <- aggregate(d[,c("GSS", "GHH", "HSS", "HHH")], by = list(group=d$k), mean)
    else
        dd <- aggregate(d[,c("GSS", "GHH", "HSS", "HHH")], by = list(group=d$group), mean)

    if (!is.na(epsfile))
        postscript(epsfile, width = 4.8, height = 4.8, paper = "special", horizontal = F)

    l <- nrow(dd)
    ylim <- c(min(min(dd[,2:5])), max(max(dd[,2:5])))
    ux <- sprintf("%.5f", min(d$right - d$left))
    uy <- sprintf("%.5f", min(d$top - d$bottom))
    par(mar=c(5, 4, 3, 2))
    if (knn)
        xlab <- "k"
    else
        xlab <- substitute(paste("Query Area (Unit Area - ", Delta, "Lon x ", Delta,
          "Lat: ", ux, " x ", uy, ")", sep = ""), list(ux=ux,uy=uy))
    plot(NA, NA, xlim = c(0, l), ylim = ylim, type = "n", ylab = "Page Access",
      xlab = xlab, xaxs = "i", yaxs = "i")
    grid()

    for (i in 1:4)
        lines(1:l, dd[,i+1], lty = i, lwd = 2)

    legend(x = "bottomright", legend = c("GSTR", "GH", "HSTR", "HH"),
      lty = 1:4, lwd = 2, cex = 0.8)

    if (!is.na(epsfile))
        dev.off()
}

rtreepack.plot.query.performance.all <-
function()
{
    rtreepack.plot.query.performance("expr/TIGER_Region_200.csv.range.result",
      epsfile = "figures/TIGER-Region-Range-Query-Low-Density.eps")
    rtreepack.plot.query.performance("expr/TIGER_Region_2000.csv.range.result",
      epsfile = "figures/TIGER-Region-Range-Query-Med-Density.eps")
    rtreepack.plot.query.performance("expr/TIGER_Region_20000.csv.range.result",
      epsfile = "figures/TIGER-Region-Range-Query-High-Density.eps")

    rtreepack.plot.query.performance("expr/Traj_Region_0.1.csv.range.result",
      epsfile = "figures/GPS-Region-Range-Query-Low-Density.eps")
    rtreepack.plot.query.performance("expr/Traj_Region_1.csv.range.result",
      epsfile = "figures/GPS-Region-Range-Query-Med-Density.eps")
    rtreepack.plot.query.performance("expr/Traj_Region_10.csv.range.result",
      epsfile = "figures/GPS-Region-Range-Query-High-Density.eps")

    rtreepack.plot.query.performance("expr/TIGER_Region_200.csv.join.result",
      epsfile = "figures/TIGER-Region-Join-Query-Low-Density.eps")
    rtreepack.plot.query.performance("expr/TIGER_Region_2000.csv.join.result",
      epsfile = "figures/TIGER-Region-Join-Query-Med-Density.eps")
    rtreepack.plot.query.performance("expr/TIGER_Region_20000.csv.join.result",
      epsfile = "figures/TIGER-Region-Join-Query-High-Density.eps")

    rtreepack.plot.query.performance("expr/TIGER_Region_200.csv.join.result",
      epsfile = "figures/TIGER-Region-Join-Query-Low-Density.eps")
    rtreepack.plot.query.performance("expr/TIGER_Region_2000.csv.join.result",
      epsfile = "figures/TIGER-Region-Join-Query-Med-Density.eps")
    rtreepack.plot.query.performance("expr/TIGER_Region_20000.csv.join.result",
      epsfile = "figures/TIGER-Region-Join-Query-High-Density.eps")

    rtreepack.plot.query.performance("expr/TIGER_Point_200.csv.knn.result",
      epsfile = "figures/TIGER-Point-kNN-Query-Low-Density.eps", knn = T)
    rtreepack.plot.query.performance("expr/TIGER_Point_2000.csv.knn.result",
      epsfile = "figures/TIGER-Point-kNN-Query-Med-Density.eps", knn = T)
    rtreepack.plot.query.performance("expr/TIGER_Point_20000.csv.knn.result",
      epsfile = "figures/TIGER-Point-kNN-Query-High-Density.eps", knn = T)
}

rtreepack.plot.scaleup <-
function()
{
    postscript("figures/Scaleup.eps", width = 4.8, height = 4.8,
      paper = "special", horizontal = F)
    d <- read.csv("expr/Scaleup.csv")
    d$total <- d$time_pre1 + d$time_pack1 + d$time_pre2 + d$time_pack2 + d$time_pack3
    algorithms <- unique(d$algo)
    plot(0, 0, xlim=c(2,12), ylim=c(min(d$total) * 0, max(d$total) * 1.2), type="n",
      xlab="Number of nodes", ylab="Execution time")
    grid()
    for (i in 1:length(algorithms)) {
        dd <- d[d$algo == algorithms[i],]
        lines(dd$nodes, dd$total, type = "o", pch = i)
    }
    legend("bottomright", pch=1:length(algorithms), legend=algorithms)
    dev.off()
}

rtreepack.plot.speedup <-
function()
{
    postscript("figures/Speedup.eps", width = 4.8, height = 4.8,
      paper = "special", horizontal = F)
    d <- read.csv("expr/Speedup.csv")
    d$total <- d$time_pre1 + d$time_pack1 + d$time_pre2 + d$time_pack2 + d$time_pack3
    algorithms <- unique(d$algo)
    plot(0, 0, xlim=c(2,12), ylim=c(1, 6), type="n",
      xlab="Number of nodes", ylab="Speedup")
    grid()
    for (i in 1:length(algorithms)) {
        dd <- d[d$algo == algorithms[i],]
        speedup <- dd$total[1] / dd$total
        lines(dd$nodes, speedup, type = "o", pch = i)
    }
    lines(c(2,12), c(1,6), lty=2)
    legend("topleft", pch=1:length(algorithms), legend=algorithms)
    dev.off()
}

rtreepack.plot.fig1 <-
function () 
{
    postscript('figures/fig1_1.eps', width=4.8, height=4.8, paper="special", horizontal=F)
    t <- read.csv('data/xorder.csv', header=F)
    rtreepack.plot.rects(t)
    dev.off()

    postscript('figures/fig1_2.eps', width=4.8, height=4.8, paper="special", horizontal=F)
    t <- read.csv('data/hilbert.csv', header=F)
    rtreepack.plot.rects(t)
    dev.off()

    postscript('figures/fig1_3.eps', width=4.8, height=4.8, paper="special", horizontal=F)
    t <- read.csv('data/str.csv', header=F)
    rtreepack.plot.rects(t)
    dev.off()
}

rtreepack.plot.rects <-
function(t)
{
    par(mar=c(0.8,0.8,0.8,0.8))
    plot(c(min(t[,2]), max(t[,3])), c(min(t[,4]), max(t[,5])), type = 'n', axes=F, xlab=NA, ylab=NA)
    rect(t[,2], t[,4], t[,3], t[,5], lwd=0.8)
    box()
}

